1225. Флаги

Флаг состоит из n вертикальных полос белого, красного и синего цвета. Соседние полосы не могут иметь одинаковый цвет, а синяя полоса всегда должна находиться между красной и белой. Сколькими способами можно покрасить флаг из n полос?

Вход. Число полос n (1 £ n £ 45) на флаге.

Выход. Количество способов, которыми можно покрасить флаг из n полос.

Пример входа

3

Пример выхода

4

РЕШЕНИЕ

числа Фибоначчи

Анализ алгоритма

Обозначим через f_red(n) и f_white(n) количество способов раскраски флага из n полос при условии, что первой полосой будет соответственно красная или белая. Тогда

f_red(n) = f_white(n – 1) + f_white(n – 2), f_red(1) = 1, f_red(2) = 1;

f_white(n) = f_red(n – 1) + f_red(n – 2), f_white(1) = 1, f_white(2) = 1.

Если f(n) – искомое общее количество способов раскраски, то

f(n) = f_red(n) + f_white(n)

Поскольку f_red(1) = f_white(1) = 1, f_red(2) = f_white(2) = 1, а f_red(n) и f_white(n) одинаковыми формулами выражаются друг через друга, то f_red(n) = f_white(n) = f_n, где f_n – n-ое число Фибоначчи. Таким образом f(n) = 2 * f_n.

Реализация алгоритма

В массиве fib вычислим значения f_red(n): f_red(n) = fib[n]. Для n > 44 значения f_red(n) будут выходить за границы типа int, поэтому воспользуемся 64 - битовым целочисленным типом __int64.

__int64 fib[46];

Читаем входное значение n. Нахождение значения fib[n] совершим в цикле:

scanf("%d",&n);

fib[1] = 1; fib[2] = 1;

for(i=3;i<=n;i++) fib[i] = fib[i-1] + fib[i-2];

Выводим результат f(n) = 2* f_red(n) = 2 * fib[n]:

printf("%I64d\n",2*fib[n]);